\documentclass[12pt, a4paper]{report}

% wow! quelqu'un est en train de lire le code source !

\usepackage{elegant-cours}

\begin{document}

\MaPageDeGarde{Chapitre XI : Arithmétiques}{Retranscrit par Samy Youssoufine}{./assets/logo.png}{Peut contenir des erreurs ou des sections incomplètes.}

\tableofcontents
\clearpage

\vspace*{\fill}
Ce chapitre est consacré à l'arithmétique dans un anneau intègre (cas général). On étudiera ensuite des cas particuliers de cette dernière.
\vspace*{\fill}

\chapter{Divisibilité dans un anneau intègre}

\section{Divisibilité et éléments associés}

\begin{definition}
    Soient $A$ un anneau intègre (commutatif) et $x,y$ des éléments de $A$. On dit que $x$ divise $y$ dans $A$ lorsqu'il existe un $a\in A$ tel que $y = xa = ax$ (sachant que la multiplication est commutative). On note alors $x\mid y$ (\textbf{pas} noté $x/y$ !).
\end{definition}

\begin{example}
    Prenons $A=\Z[i]$ l'anneau des entiers gaussiens. Cet anneau est intègre parce que c'est un sous-anneau de $\C$, qui est intègre, parce que $\C$ est un corps.

    On cherche les diviseurs de $2$ dans $\Z[i]$. On remarque que $2 = (1+i)(1-i)$, donc $1+i$ et $1-i$ divisent $2$. On peut aussi remarquer que $2 = (-i)(-2i)$, donc $-2i$ divise aussi $2$.

    Nous allons maintenant rechercher tous les diviseurs de $2$ dans $\Z[i]$.

    Soit $x=a+ib \in \Z[i]$ un diviseur de $2$. Alors il existe un $y = c+id$ tel que $xy=2 \iff (a+ib)(c+id)=2$.

    On utilise le module pour trouver des contraintes sur $a$ et $b$ :
    \[
        \underbrace{(a^2+b^2)}_{\in\N}\underbrace{(c^2+d^2)}_{\in\N} = |xy|^2 = |2|^2 = 4.
    \]

    Cela implique que $a^2+b^2$ divise $4$ dans $\N$. Cela implique que $a^2+b^2 \in \{1,2,4\}$ (car $a^2+b^2$ est une somme de carrés d'entiers).

    \begin{itemize}
        \item Si $a^2+b^2=1$, alors $(a,b) \in \{(\pm 1,0),(0,\pm 1)\}$. Cela donne les diviseurs $1,-1,i,-i$.
        \item Si $a^2+b^2=2$, alors $(a,b) \in \{(\pm 1,\pm 1)\}$. Cela donne les diviseurs $1+i, 1-i, -1+i, -1-i$.
        \item Si $a^2+b^2=4$, alors $(a,b) \in \{(\pm 2,0),(0,\pm 2)\}$. Cela donne les diviseurs $2,-2,2i,-2i$.
    \end{itemize}

    La réciproque est facile à vérifier. Ainsi, les diviseurs de $2$ dans $\Z[i]$ sont :

    \[
        \{\pm 1, \pm i, \pm (1+i), \pm (1-i), \pm 2, \pm 2i\}.
    \]
\end{example}

\begin{importantbox}
    Dans la suite de cette partie, toute mention de $(A,+,\times)$ désignera un anneau intègre commutatif.
\end{importantbox}

\begin{property}
    \label{property:divisibilite}
    \begin{enumerate}
        \item Pour tout $x\in A$, on a $x\mid x$ (réflexivité).
        \item Pour tout $x,y,z \in A$, si $x\mid y$ et $y\mid z$, alors $x\mid z$ (transitivité).
        \item Pour tout $x,y\in A$, $x\mid y \iff yA \subset xA$. Il faut faire attention à ne pas inverser les deux membres ! Cette relation nous permet de passer de la relation de divisibilité à une inclusion (inégalité).
        \item Pour tout $x,y \in A, (x\mid y \et y \mid x) \iff xA = yA$. Cela équivaut à dire que $\exists \eps \in \mathbb{U}_A \tq x = \eps y$. On dit que $x$ et $y$ sont \textbf{associés} dans ce cas.
        \item La relation de divisibilité n'est pas antisymétrique. Par exemple, dans $\Z$, $2\mid -2$ et $-2\mid 2$, mais $2 \neq -2$.
        \item La relation de divisibilité n'est pas symétrique, par exemple dans $\Z$, $2\mid 4$, mais $4 \nmid 2$.
        \item La relation de divisibilité n'est donc pas une relation d'équivalence.
    \end{enumerate}
\end{property}

\begin{proof}
    \begin{enumerate}
        \item Trivial car $x = x \cdot 1_A$.
        \item $(x \mid y)$ et $(y \mid z)$ impliquent l'existence de $a,b \in A$ tels que $y = xa$ et $z = yb$. Donc $z = (xa)b = x(ab)$, donc $x \mid z$.
        \item ($\impliedby$) : On a $y=y\cdot 1_A \in yA \subset xA$, donc $y \in xA \iff \exists a \in A \tq y = ax$, donc $x\mid y$.\\($\implies$) : Supposons que $x\mid y$, alors $\exists a \in A \tq y = ax$. Soit $t \in yA$, i.e. $\exists \alpha \in A \tq t = y\alpha$.\\Donc $t = (ax)\alpha = x\underbrace{(a\alpha)}_{\in A} \in xA$. Ainsi, $yA \subset xA$.
        \item D'après la propriété précédente, $x\mid y$ et $y \mid x$ équivaut à $yA \subset xA$ et $xA \subset yA$, donc $xA = yA$.\\Maintenant, nous allons montrer que $(x \mid y \et y \mid x) \iff \exists \eps \in \mathbb{U}_n \tq x = \eps y$.\\Dans le sens réciproque, on a $x=\eps y \implies y \mid x$, or $\eps \in \mathbb{U}_A \implies \exists \eps' \in \mathbb{U}_A \tq \eps'x=y$. D'où $x\mid y$.\\Dans le sens direct, on suppose que $x\mid y$ et $y \mid x$. Donc il existe $t,z \in A \tq y=tx \et x=zy$.\\Donc $y=t(zy) = (tz)y$. Donc $y(1_A - tz) = 0_A$. Comme $A$ est intègre, cela veut dire que $y=0_A$ ou $1_A - tz = 0_A \iff tz = 1_A$. Dans le deuxième cas, cela veut dire que $tz=1_A$, donc $z=\eps \in \mathbb{U}_A$, et on a bien $x = zy = \eps y$. Dans le premier cas, on a $y=0_A$, donc $x=zy= z0_A = 0_A$. On peut alors choisir $\eps = 1_A \in \mathbb{U}_A$ et on a bien $x=\eps y$.\\Ainsi, dans tous les cas, on a $\exists \eps \in \mathbb{U}_A \tq x = \eps y$.
    \end{enumerate}
\end{proof}

\begin{example}
    \begin{enumerate}
        \item $\mathbb{U}_\Z = \{-1,1\}$. Donc, dans $\Z$, $(x\mid y \et y \mid x) \iff \exists \eps \in \{-1,1\} \tq x = \eps y$. Cela équivaut à dire que $x=\pm y$, ou que $|x|=|y|$.
        \item Dans $\Z[i]$, on a $\mathbb{U}_{\Z[i]} = \{1,-1,i,-i\}$. Donc, dans $\Z[i]$, $(x\mid y \et y \mid x) \iff \exists \eps \in \{1,-1,i,-i\} \tq x = \eps y$.
    \end{enumerate}
\end{example}

\section{Idéaux/anneaux principaux et PGCD}

\begin{definition}[Anneau principal]
    \begin{enumerate}
        \item Soit $I$ un idéal de $A$, $I$ est un \textbf{idéal principal} de $A$ lorsque $I$ est engendré par un seul élément $x$ de $A$. i.e. $I$ est un idéal principal $\iff \exists x \in A \tq I = xA$.
        \item Un anneau $A$ est dit principal lorsque tout les idéaux sont principaux. i.e. $\forall I \text{ idéal de } A, \exists x \in A \tq I = xA$.
    \end{enumerate}
\end{definition}

% peut ne pas être intègre

\begin{attention}
    Un anneau principal n'est pas forcément un anneau intègre. Par exemple, $\Z/6\Z$ est un anneau principal (voir exemple plus bas), mais ce n'est pas un anneau intègre car $\overline{2} \times \overline{3} = \overline{0}$ dans $\Z/6\Z$.
\end{attention}

\begin{example}
    \begin{enumerate}
        \item $\Z$ est un anneau principal.
        \item Tout corps est un anneau principal parce que les seuls idéaux sont $\{0\}$ et le corps lui-même, qui sont tous deux principaux.
        \item On a déjà vu que les idéaux de $\Z/4\Z$ sont $\{0\}, 2\Z/4\Z$ et $\Z/4\Z$, qui sont tous des idéaux principaux. Donc $\Z/4\Z$ est un anneau principal.
    \end{enumerate}
\end{example}

\begin{exercise}
    Montrer que $\Z/6\Z$ est un anneau principal.
\end{exercise}

\begin{theorem}[PGCD dans un anneau principal]
    Soient $A$ un anneau principal et $x_1,\dots,x_n \in A$. Alors il existe un $d \in A$ tel que :

    $$x_1 A + x_2 A + \dots + x_n A = dA$$

    avec $\forall i \in [\![1,n]\!], d \mid x_i$.

    De plus, si $d'$ est un autre élément de $A$ vérifiant ces propriétés, alors $d' \mid d$.

    Dans cas, $d$ est appelé le \textbf{plus grand commun diviseur} (PGCD) des $x_i$.

    On le note $\pgcd(x_1,\dots,x_n)$.
\end{theorem}

\begin{proof}
    \begin{itemize}
        \item On a $\forall i \in [\![1,n]\!], x_iA$ est un idéal principal.
        \item Donc $\sum_{i=1}^{n}x_iA = x_1A + \dots + x_nA$ est aussi un idéal de $A$, qui est principal, puisque l'anneau $A$ est principal.
        \item Donc $\exists d \in A \tq \sum_{i=1}^{n}x_iA = dA$.
        \item On a $\forall i \in [\![1,n]\!], x_i = x_i\times 1_A + \sum_{j=1\et j\neq i}^{n}x_j \times 0_A \in \sum_{i=1}^{n}x_iA = dA$.
        \item Donc $\forall i \in [\![1,n]\!], d \mid x_i$.
        \item Si $d' \in A \tq \forall i \in [\![1,n]\!], d' \mid x_i$.
        \item Alors $\forall i \in [\![1,n]\!], x_iA \subset d'A$.
        \item Comme $dA$ est stable par l'addition (sous-groupe), alors $dA = \sum_{i=1}^{n}x_iA \subset d'A \implies d'|d$.
    \end{itemize}
\end{proof}

\begin{remark}[Non unicité du PGCD]
    Si $d$ est un PGCD de $x_i$, alors tout autre PGCD $d'$ est associé à $d$. En effet, on a $d' \mid d$ et $d \mid d'$. Ils peuvent s'écrire sous la forme de $d' = \eps d$ avec $\eps \in \mathbb{U}_A$.
\end{remark}

\begin{remark}
    $\Z$ est un anneau principal, donc $\forall x_1,\dots,x_n \in \Z,\exists d \in \Z \tq x_1\Z + \dots + x_n\Z=d\Z$. Or, tous les pgcd des $(x_i)_{1\leq i \leq n}$ sont $\pm d$.

    Alors, $\forall x_1,\dots,x_n \in \Z, \exists! d \in \N \tq \sum_{i=1}^n x_i\Z = d\Z$.

    Dans ce cas, $d$ est appelé \underline{le} PGCD des $x_i$ dans $\Z$.
\end{remark}

\begin{theorem}[Égalité de Bézout]
    Soient $A$ un anneau principal et $x_1,\dots,x_n \in A$. Alors, si $d$ est un $\pgcd(x_1,\dots,x_n)$, alors :
    \[
        \exists u_1,\dots,u_n \in A \tq d = u_1 x_1 + u_2 x_2 + \dots + u_n x_n.
    \]
\end{theorem}

\begin{proof}
    On a $\sum_{i=1}^{n}x_iA = dA$. Donc, $d\in dA = \sum_{i=1}^{n}x_iA$. 
\end{proof}

\begin{property}[Réciproque de l'égalité de Bézout]
    Soient $x_1,\dots,x_n \in A$ (anneau principal), et $d$ un élément de $A$ tel que $\exists u_1,\dots,u_n \in A \tq d = u_1 x_1 + u_2 x_2 + \dots + u_n x_n$.

    $d$ n'est pas forcément le PGCD des $x_i$. Il faut que $d$ soit un diviseur commun des $x_i$ pour que $d$ soit le PGCD des $x_i$.
    
\end{property}

\begin{proof}
    Montrons que $\sum_{i=1}^{n}x_iA = dA$.

    Montrons d'abord l'inclusion $\sum_{i=1}^{n}x_iA \subset dA$.

    Soit $y\in dA$. DOnc $y=da$ pour un certain $a\in A$.

    Donc $y = (\sum_{i=1}^{n}x_iu_i)a=\sum_{i=1}^{n}x_i\underbrace{(u_i a)}_{\in A}$

    Donc $y \in \sum_{i=1}^{n}x_iA$.

    i.e. : $dA \subset \sum_{i=1}^{n}x_i A$.

    On conclut que $\sum_{i=1}^{n}x_iA = dA$.

    D'où $d=\pgcd(x_1,\dots,x_n)$.
\end{proof}

\begin{consequence}[Théorème de Bézout pour le PGCD]
    Soient $x_1,\dots,x_n \in A$ principal.

    $\pgcd(x_1,\dots,x_n)=1_A \iff \exists u_1,\dots,u_n \in A \tq \sum_{i=1}^{n}x_iu_i=1_A$.

    On dit que les $x_i$ sont \textbf{premiers entre eux} dans ce cas.
\end{consequence}

\begin{theorem}[Théorème de Gauss]
    Soient $A$ un anneau principal et $x,y,z \in A$ tels que $x \mid yz$ et $\pgcd(x,z)=1_A$. Alors $x \mid y$.
    
\end{theorem}

\begin{proof}
    On a $x\mid yz$, donc $\exists a \in A \tq yz = xa$.

    On sait aussi que $\pgcd(x,z)=1_A$, cela équivaut à dire que $\exists u_1,u_2 \in A \tq 1_A = u_1 x + u_2 z$.

    Donc $y= xyu_1+yzu_2$.

    Donc $y= xyu_1 + (xa)zu_2 = x\underbrace{(yu_1 + au_2 z)}_{\in A}$.
    
    Donc $x \mid y$.
\end{proof}

\begin{consequence}
    \label{consequence:pgcd_produit}
    Soient $y_1,\dots,y_n$ et $x_1,\dots,x_n$ des éléments de $A$.

    On a :

    $$\parens{\forall i,j \in [\![1,n]\!], \pgcd(x_i,x_j)=1_A} \iff \parens{\prod_{i=1}^n x_i}\wedge \parens{\prod_{i=1}^n y_i} = 1_A$$
\end{consequence}

\begin{property}
    Soient $x,y,z \in A$ (anneau principal).

    $$(x\wedge y = x \wedge z= 1_A) \iff x\wedge (yz) = 1_A$$
\end{property}

\begin{proof}
    \begin{enumerate}
        \item ($\impliedby$) : Facile.
        \item ($\implies$) : On a $\exists u_1,u_2,v_1,v_2 \in A \tq \begin{cases}xu_1 + y u_2 = 1_A\\xv_1 + z v_2 = 1_A\end{cases}$
        \item Cela implique que $x(\underbrace{xu_1v_1+zu_1v_2+yu_2v_1}_{\in A}) + yz(u_2v_2) = 1_A$.
        \item Donc $x \wedge (yz) = 1_A$.
    \end{enumerate}
\end{proof}

\begin{proof}[Démonstration de la conséquence \ref{consequence:pgcd_produit}]
    En utilisant la propriété précédente, on peut
    
\end{proof}
\todo{recop}

\begin{application}
    Montrer que $\sqrt[3]{2}$ n'appartient pas à $\Q$.

    \textbf{Solution :}

    Supposons que $\sqrt[3]{2} \in \Q$. 
    
    Alors, il existe $(p,q)\in\Z\times\N^*$ tels que $\sqrt[3]{2} = \frac{p}{q}$ et $\pgcd(p,q) = 1$.

    On a donc $2q^3 = p^3$.

    Donc $q^3 \mid p^3$.

    Donc $\pgcd(p^3,q^3) = 1$ (car $\pgcd(p,q)=1$).

    Or, comme $q^3 \mid p^3$ et $\pgcd(p^3,q^3)=1$, d'après le théorème de Gauss, on a $q^3 \mid 1$, donc $q=1$.

    Donc $p^3 = 2$.

    Or $1<2<8=2^3$, donc $1^3<p^3<2^3$, donc $1<p<2$, ce qui est impossible.

    Donc $\sqrt[3]{2} \notin \Q$.
\end{application}

\begin{property}
    Soient $A$ un anneau principal et $x,y,z$ dans $A$.

    Si $x\mid y$ et $y\mid z$ avec $\pgcd(x,y)=1_A$, alors $xy \mid z$.
\end{property}

\begin{proof}
    On sait que $\exists a,b \in A \tqp z = xa$ et $z=yb$.

    Donc $\exists u,v \in A \tqp xu + yv = 1_A$.

    \begin{align*}
        \implies z &= z(xu + yv)\\
        &= xybu + xyav = xy(bu + av)\\
        &implies xy \mid z.
    \end{align*}
\end{proof}

\begin{consequence}
    Si $x_1,\dots,x_n,z \in A$ (avec $A$ un anneau principal). On a :

    $$\begin{cases}
        \forall i \in [\![1,n]\!], x_i \mid z\\
        \forall i,j \in [\![1,n]\!], \pgcd(x_i,x_j) = 1_A
    \end{cases} \implies \prod_{i=1}^n x_i \mid z$$
\end{consequence}

\begin{proof}
    On procède par récurrence sur $n$.
\end{proof}

\begin{remark}
    En général, $\begin{cases}
    x\mid z\\y\mid z
    \end{cases} \nimplies xy \mid z$.

    (On prend comme contre-exemple $4\mid 12$ et $6\mid 12$...)
\end{remark}

\begin{property}
    Soient $t,x,y \in \Z$.

    On a $(tx)\wedge (ty) = |t| (x \wedge y)$.
\end{property}

\begin{proof}
    On pose $d=(tx)\wedge (ty)$.

    On a alors $(tx)\Z + (ty)\Z = d\Z$ (définition du PGCD dans $\Z$).

    Ce qui implique que $t(x\Z + y\Z) = d\Z$ (opérations sur les ensembles).

    Donc $t(x \wedge y)\Z = d\Z$.

    Donc $|t(x \wedge y)| = d$ (car ces deux entiers sont associés, voir propriété \ref{property:divisibilite}).

    Donc $d = |t| (x \wedge y)$.
\end{proof}

\begin{property}
    Soient $A$ un anneau principal et $x,y \in A$.

    $$x\wedge y = d \iff \exists x_1,y_1 \in A \tq \begin{cases}
        x = dx_1\\
        y= dy_1\\
        x_1 \wedge y_1 = 1_A
    \end{cases}$$
\end{property}

\begin{proof}
    Dans le sens direct $(\implies)$, on suppose que $d\mid x$ et $d\mid y$.

    Donc $\exists x_1,y_1 \in A \tq x=dx_1$ et $y=dy_1$.

    Or $x\wedge y = d = (dx_1) \wedge (dy_1)$

    Donc $d = d(x_1 \wedge y_1)$.

    Alors $d(1_A - (x_1 \wedge y_1)) = 0_A$.

    Si $d = 0_A$, alors $x=y=0_A$, donc on peut choisir $x_1=y_1=1_A$ et on a bien $x_1 \wedge y_1 = 1_A$.

    Si $d \neq 0_A$, comme $A$ est intègre, on a $1_A - (x_1 \wedge y_1) = 0_A$, donc $x_1 \wedge y_1 = 1_A$.

    Dans le sens réciproque $(\impliedby)$, on a $x=dx_1$ et $y=dy_1$.

    On sait que $x_1 \wedge y_1 = 1_A$.

    Donc $\exists u,v \in A \tq 1_A = u x_1 + v y_1$.

    Donc $d = d(u x_1 + v y_1) = u (dx_1) + v (dy_1) = ux + vy$.

    Donc $x \wedge y = d$.
\end{proof}

\chapter{Divisibilité dans $\Z/n\Z$}

\section{Rappels et compléments sur $\Z/n\Z$}

\begin{remark}
    \begin{enumerate}
        \item Soient $x,y \in \Z^* \tqp x \mid y$. On a donc $-x\mid y$, on prendra donc toujours $x \in \N^*$ sans perte de généralité. Donc $x\mid y \iff \overline{y} = \overline{0}$ dans $\Z/x\Z$.
        \item $\Uset_{\Z/n\Z} = \{\ovl{x} \tq x \wedge n = 1\}$.\\On rappelle le théorème de Gauss dans $\Z$ : $(x\mid yz \et x \wedge y =1)\implies x \mid z$.
    \end{enumerate}
\end{remark}

\begin{proof}
    On a $x\mid yz \iff \ovl{\ovl y \cdot \ovl z} = \ovl 0$ dans $\Z/|x|\Z$.

    \begin{align*}
        \ona x\wedge y = 1 &\iff \ovl y \in \Uset_{\Z/|x|\Z}\\
        \text{Hypothèse de départ} &\implies \ovl y \cdot \ovl z = \ovl 0 \text{ dans } \Z/|x|\Z\\
        \implies \ovl y^{-1} \cdot \ovl y \cdot \ovl z &= \ovl y^{-1} \cdot \ovl 0\\
        \ovl z &= \ovl 0 \text{ dans } \Z/|x|\Z\\
        \implies x \mid z.
    \end{align*}
\end{proof}

\begin{exercise}
    \begin{enumerate}
        \item Montrer que $\forall n \in \N, 6 \mid n^3 - n$.
        \item Pour quelles valeurs de $n \in \N$ a-t-on $11 \mid n^3 + n$ ?
    \end{enumerate}

    \textbf{Solution :}

    \begin{enumerate}
        \item On peut tout simplement démontrer qu'il s'agit d'un produit de trois nombres consécutifs, dont un est forcément pair. Mais on peut aussi faire ce calcul :\\$\legbinom{3}{n+1}=\dots=\frac{(n-1)n(n+1)}{6} \in \N$.\\ Donc $6 \mid n^3 - n$.
        \item $11\mid n^3+n \iff \ovl n (\ovl{n^2+1}) = \ovl 0$ dans $\Z/11\Z$.\\On dresse un tableau des carrés dans $\Z/11\Z$. On trouve que $11 \mid n^3 + n$ lorsquee $\ovl n (\ovl{n^2 +1}) = \ovl 0$. C'est-à-dire lorsque $\ovl n = \ovl 0$ dans $\Z/11\Z$ (le cas $\ovl{n^2+1}=\ovl 0$ n'ayant pas de solution). Donc $11 \mid n^3 + n \iff 11 \mid n$.
    \end{enumerate}
\end{exercise}

\begin{property}[Divisibilité par 3]
    Soit $x=a_n\dots a_0$ l'écriture en base décimale de $x \in \N$.

    $$3 \mid x \iff 3 \mid \sum_{k=0}^{n}a_k$$
\end{property}

\begin{proof}
    On a $x=\sum_{k=0}^{n}a_k\cdot 10^k$.

    \begin{align*}
        \ona 3\mid x &\iff \ovl x = \ovl 0 \text{ dans } \Z/3\Z\\
        &\iff \sum_{k=0}^{n}\ovl{a_k \cdot 10^k} = \ovl 0 = \ovl{\sum_{k=0}^{n}a_k} \text{ dans } \Z/3\Z\\
        &\iff \sum_{k=0}^{n}\ovl{a_k} = \ovl 0 \text{ dans } \Z/3\Z\\
        &\iff 3 \mid \sum_{k=0}^{n}a_k
    \end{align*}
\end{proof}

\section{Division euclidienne et algorithme d'Euclide}

\begin{theorem}[Division euclidienne]
    Soient $(x,y)\in\Z\times\Z^*$.

    Alors $\exists!(q,r)\in\Z\times\N \tqp : \begin{cases}
    x=qy+r\\
    0 \leq r < |y|
    \end{cases}$

    On dit qu'on a effectué la division euclidienne (qu'on notera D.E.) de $x$ par $y$.

    \begin{itemize}
        \item $q$ est appelé le \textbf{quotient} de la D.E. de $x$ par $y$.
        \item $r$ est appelé le \textbf{reste} de la D.E. de $x$ par $y$.
    \end{itemize}
    
\end{theorem}

\begin{proof}
    \begin{align*}
        \begin{cases}
            x = qy + r\\
            0 \leq r < |y|
        \end{cases} &\iff \begin{cases}
        r = x-qy\\
        0 \le x - qy < |y|
        \end{cases}\\
        &\iff \begin{cases}
        r = x - qy\\
        0 \le \frac{x}{|y|} - q \frac{y}{|y|} < 1
        \end{cases}
    \end{align*}

    Si $y > 0$, alors on a $\begin{cases}
    r = x-qy\\
    0 \le \frac{x}{y} - q < 1
    \end{cases}$

    On prend $q=E(\frac{x}{y}) \in \Z$, et $r = x-qy \in \N^*$.

    Si $y < 0$, alors on a $\begin{cases}
    r = x-qy\\
    -q \le -\frac{x}y < 1 - q
    \end{cases}$

    Donc on prend $q = -E(-\frac{x}{y}) \in \Z$, et $r = x-qy \in \N^*$.

    D'où l'existence et l'unicité de $(q,r)$.
\end{proof}

\begin{property}
    Soient $(x,y) \in \Z \times\Z^*$.

    On a $\exists!(q,r)\in\Z\times\N^* \tqp \begin{cases}
    x=qy+r\\
    0 < r \leq |y|
    \end{cases}$

    Le PGCD de $x$ et $y$ est égal au PGCD de $y$ et $r$.

    $$x\wedge y = y \wedge r$$
\end{property}

\begin{proof}
    On pose $d=x\wedge y$, et $d' = y \wedge r$.

    \textbf{Méthode 1 (plus facile) en utilisant les combinaisons linéaires :} (non abordée).

    \textbf{Méthode 2 en utilisant la définition du PGCD :}

    \begin{align*}
        d\Z &= x\Z + y\Z\\
        &= (qy+r)\Z + y\Z\\
        &\subset r\Z + y\Z=d'\Z\\
    \end{align*}

    De même, $d'\Z = y\Z + r\Z \subset x\Z + y\Z = d\Z$.

    Donc $|d| = |d'| \implies d = d'$ car ils sont positifs.

    On en déduit que $x \wedge y = y \wedge r$.

\end{proof}

\begin{application}[Algorithme d'Euclide]
    Cet algorithme nous permet de déterminer le PGCD de deux entiers $a$ et $b$ ainsi que leurs coefficients de Bézout.

    Soit $(a,b) \in \Z\times\N^*$.

    \begin{itemize}
        \item Si $b\mid a$ alors $a\wedge b = b$.
        \item Sinon, $a=bq+r_1$ avec $0<r_1< b$ (après division euclidienne).
        \item Donc $a\wedge b = b \wedge r_1$.
        \item Si $r_1 \mid b$ alors $a\wedge b = r_1$.
        \item Sinon, $b = r_1 q_2 + r_2$ avec $0 < r_2 < r_1$.
        \item Donc $a\wedge b = r_1 \wedge r_2$.
        \item On continue ainsi jusqu'à obtenir un reste $r_n$ qui divise le précédent.
    \end{itemize}

    On a donc construit une suite de restes $(r_n)_{n\ge1}$. Ce processus doit s'arrêter car les restes sont strictement décroissants et positifs. Si le processus ne s'arrête pas, on aurait une suite infinie de restes strictement positifs et décroissants, ce qui est impossible dans $\N$, car la suite doit être stationnaire à partir d'un certain rang.

    Le dernier reste non nul $r_n$ est le PGCD de $a$ et $b$.
\end{application}

\begin{example}
    Calculer le PGCD de $a = 60$ et $b=42$.

    On a $a=60=1\times42+18$.
    Et on a $b = 42 = 2\times 18 + 6$.
    Enfin, on a $18 = 3 \times 6 + 0$.
    Donc le PGCD de $60$ et $42$ est $6$.

    Nous allons retrouver les coefficients de Bézout associés.

    On a $6 = 42 - 2 \times 18$.

    Or, $18 = 60 - 1 \times 42$.

    Donc $6 = 42 - 2 \times (60 - 1 \times 42) = 3 \times 42 - 2 \times 60$.

    Ainsi, les coefficients de Bézout sont $u = -2$ et $v=3$.
\end{example}

\begin{property}[Équation $ax+by=c$]
    Soient $A$ un anneau principal et $a,b,c \in A \tq (a,b)\neq (0_A,0_A)$.

    On pose $d = a \wedge b$.

    Les solutions de l'équation $ax + by = c$ sont données par :
    $$\begin{cases}
        \si d \nmid c, \text{ il n'y a pas de solution}\\
        \si d \mid c, \exists \text{ une solution }(x_0,y_0) \et S= \{(x,y) = (x_0 + \frac{b}{d}k, y_0 - \frac{a}{d}k) \text{ avec } k \in A\}
    \end{cases}$$
    
\end{property}

\begin{proof}
    \begin{align*}
        a \wedge b = d &\iff \exists a_1,b_1 \in A \tqp a = da_1 \et b = db_1 \et a_1 \wedge b_1 = 1_A\\
    \end{align*}

    Donc $(E) : d(a_1 x + b_1 y) = c$.

    Dans le cas où $d\nmid c$, il n'y a pas de solution.

    Dans le cas contraire, on a $c = d c_1$ avec $c_1 \in A$.

    On va donc trouver l'équation $(E) : a_1 x + b_1 y = c_1$, sachant que l'anneau $A$ est intègre (donc on peut factoriser par $d$, puis omettre le cas où $d=0$, parce que $d$ est un élément non nul).

    Comme $a_1 \wedge b_1 = 1_A$, il existe un certain couple $(u,v)$ tels que $a_1 u + b_1 v = 1_A$.

    En multipliant par $c_1$, on a $a_1 (c_1 u) + b_1 (c_1 v) = c_1$.

    Donc $(x_0,y_0) = (c_1 u, c_1 v)$ est une solution particulière de $(E)$.

    Soit $(x,y)$ une autre solution de $(E)$.

    On obtient le système suivant :

    $$\begin{cases}
    a_1 x + b_1 y = c_1\\
    a_1 x_0 + b_1 y_0 = c_1
    \end{cases}\implies
    a_1(x - x_0) = b_1 (y - y_0)
    $$

    \begin{center}
    \textit{(Attention : à partir de ce stade, on ne travaille que par implications...)}
    \end{center}

    Cela implique que $b_1 \mid a_1 (x - x_0)$.

    Cela implique que $b_1 \mid (x - x_0)$ car $a_1 \wedge b_1 = 1_A$ (théorème de Gauss).

    Donc $\exists k \in A \tq x - x_0 = b_1 k$.

    Donc $\exists k \in A \tq x = x_0 + b_1 k$.

    En remplaçant dans l'équation $a_1 (x - x_0) = b_1 (y - y_0)$, on obtient :

    \begin{align*}
        a_1 (b_1 k) &= b_1 (y - y_0)\\
        \implies a_1 k &= y - y_0 \scq b_1 \ne 0 \et A \text{ est un anneau intègre }\\
        \implies y &= y_0 + a_1 k
    \end{align*}

    On trouve ensuite que toutes les solutions de l'équation $(E)$ sont de la forme :

    $$(x,y) = (x_0 + b_1 k, y_0 - a_1 k) \text{ avec } k \in A$$

    \textbf{Maintenant, on doit procéder dans le sens réciproque (il ne faut pas oublier qu'on a procédé par implications).}

    On a $a(x_0 + b_1 k) + b(y_0 - a_1 k) = d(a_1 u c_1 + a_1 b_1 k + b_1 v c_1 - b_1 a_1 k) = d(a_1 u c_1 + b_1 v c_1) = d c_1 = c$.

    On conclut que toutes les solutions de l'équation $(E)$ sont de la forme (dans le cas où $d \mid c$) :

    $$S = \{(x,y) = (x_0 + \frac{b}{d}k, y_0 - \frac{a}{d}k) \tq k \in A\}$$

    Où $(x_0,y_0)$ est une solution particulière de l'équation $ax + by = c$.

    Évidemment, la notation $\frac{a}{d}$ et $\frac{b}{d}$ est valide car $d \mid a$ et $d \mid b$, mais elle n'est pas rigoureuse. Pour être rigoureux, il faudrait écrire $a_1$ et $b_1$ à la place de $\frac{a}{d}$ et $\frac{b}{d}$, en mentionnant le fait qu'ils existent etc...

\end{proof}

\begin{example}
    Résolvons dans $\Z^2$ l'équation $(E) : 17x + 7y = 1$.

    On a $17 \wedge 7 = 1$.

    avec l'algorithme d'Euclide, on trouve :

    $17 \times (-2) + 7 \times 5 = 1$.

    Donc une solution particulière est $(x_0,y_0) = (-2,5)$.

    On peut donc écrire :
    $$\begin{cases}
        17x + 7y = 1\\
        17x - 2 +7\times 5 = 1
    \end{cases}\implies 17(x+2) = 7(5-y)$$

    Comme $7 \wedge 17 = 1$, on a $7 \mid (x+2) \implies \exists k \in \Z \tq x + 2 = 7k \implies x = -2 + 7k$.

    Cela implique que $17 \times 7k = 7(5-y) \implies 17k = 5 - y \implies y = 5 - 17k$.

    Réciproquement, on vérifie que $17(-2 + 7k) + 7(5 - 17k) = 1$.

    Donc l'ensemble des solutions de l'équation $(E)$ est :
    $$S = \{(x,y) = (-2 + 7k, 5 - 17k) \tq k \in \Z\}$$
\end{example}

\chapter{Nombres premiers}

\section{Définition et propriétés}

\begin{definition}[Nombre premier]
    Soit $p \in \N^*\setminus\{1\}$.

    $p$ est dit \textbf{nombre premier} si ses seuls diviseurs sont $1$ et $p$.

    On notera par $\mathcal{P}$ l'ensemble des nombres premiers.
\end{definition}

\begin{theorem}[Lemme]
    $\forall a \in \N^*\setminus\{1\}, \exists p \in \mathcal{P} \tq p \mid a$.
\end{theorem}

\begin{proof}
On pose $E = \{k\in\N^* \setminus \{1\} \tq \forall p \in \mathcal{P}, k \mid a\}$.

On a $q \in E \implies E \neq \emptyset$.

Donc $E \subset \N^*$.

Alors $E$ admet un minimum $p$.

Supposons que $p$ ne soit pas premier. On aura alors :

$\exists 1 < q < p \tq q \mid p$. Or $p \mid a$, alors :

$q \mid a \et q \in \N^* \setminus \{1\} \implies q \in E$.

Ce qui implique que $q\ge \min(E) = p$. Contradiction.

DOnc $p$ est premier et divise $a$.

\end{proof}

\begin{property}[Infinité des nombres premiers]
    Il existe une infinité de nombres premiers. L'ensemble $\mathcal{P}$ est infini.
\end{property}

\begin{proof}
    Supposons que $\mathcal{P}$ soit fini, et notons-le $\mathcal{P} = \{p_1,\dots,p_r\}$, avec chaque $p_i$ deux à deux distincts.

    On pose $a = 1 + \prod_{k=1}^{r} p_k > p_i \forall i \in \{1,\dots,r\}$.

    Donc $\begin{cases}
    a \notin \mathcal{P}\\
    a > 1
    \end{cases}\et \exists j \in \{1,\dots,r\} \tq p_j \mid a$.

    Or $\forall j \in \{1,\dots,r\}, p_j \wedge a = 1$, ce qui implique que $p_j 1$ car $p_j \mid a$. C'est une contradiction.

    Donc $\mathcal{P}$ est infini.
\end{proof}

\begin{remark}
    \begin{enumerate}
        \item $\forall p \in \Pset, \forall x \in\Z$, $p\wedge x = \begin{cases}
            p & \si p \mid x\\
            1 & \text{sinon}
        \end{cases}$, i.e. : Soit $p\mid x$, soit $p$ et $x$ sont premiers entre eux.
        \item Soient $p \in \Pset$. On a alors $\forall k \in \{1,\dots,p-1\}, p \mid \legbinom kp$.
    \end{enumerate}
\end{remark}

\begin{proof}
    \textbf{Preuve du deuxième point :}

    On a $\legbinom kp = \frac{p!}{k!(p-k)!}$.

    Donc $\legbinom kp = \frac pk \times \legbinom{k-1}{p-1}$.

    Donc $k\legbinom kp = p \times \legbinom{k-1}{p-1}$.

    Donc $p \mid k \legbinom kp$.

    Or, comme $1 \le k \le p-1$, on a $p \wedge k = 1$.

    Donc $d = p \wedge k = 1$.
\end{proof}

\begin{application}
    \begin{enumerate}
        \item Si $p \in \Pset \tq p \mid xy$, alors $p \mid x$ ou $p \mid y$. Car si $p \nmid x$, alors $p \wedge x = 1$, donc $p \mid y$ (théorème de Gauss), et si $p \mid x$, c'est trivial.
    \end{enumerate}
\end{application}

\section{Théorème de Fermat}

\begin{theorem}[Théorème de Fermat]
    $$\forall n \in \Z,\forall p \in \Pset, n^p \equiv n [p]$$
\end{theorem}

\begin{proof}[Preuve classique par récurrence]
    
\end{proof}
\todo{a faire pour jeudi, çàd dem1}

\begin{proof}[Preuve utilisant des notions de structures algébriques]
    \begin{center}
        On rappelle que si $(G,\cdot)$ est un groupe fini de cardinal $n \in \N^*$, alors $\forall a \in G, a^n = e$.
    \end{center}

    On sait que $(\Uset_{\Z/p\Z}, \times)$ est un groupe fini de cardinal $p-1$.

    On a $\forall n \in \Z$, \textbf{si $p\mid n$}, alors $\ovl n = \ovl 0$ et $\ovl n^p = \ovl 0 = \ovl n$. Cela implique que $n^p \equiv n [p]$.

    Le théorème est donc vrai dans ce cas.

    \textbf{Si $p \nmid n$}, c'est-à-dire que $n\wedge p = 1$, alors $\ovl n \in \Uset_{\Z/p\Z}$.

    Donc $\ovl n^{p-1} = \ovl 1$ (car le cardinal de $\Uset_{\Z/p\Z}$ est $p-1$).

    Cela implique que $\ovl n^p = \ovl n$.

    D'où $n^p \equiv n [p]$.

    Le théorème est donc vrai dans ce cas aussi.
\end{proof}

\begin{remark}
    $\forall n \in \Z, \forall k \in \N^*\setminus\{1\} \tqp n \wedge k =1$, alors $n^{\phi(k)} \equiv 1 [k]$, où $\phi$ est la fonction indicatrice d'Euler.

    On a aussi : $n\wedge k = 1 \implies \ovl n \in \Uset_{\Z/k\Z}$.
\end{remark}

\begin{exercise}
    Déterminer le reste de la division euclidienne de $5^{160}$ par $77$.

    \textbf{Solution :}

    On a $5^{10} \equiv 1[11]$ (car $5 \wedge 11 = 1$ et $\phi(11) = 10$).

    Et on a $5^6 \equiv 1[7]$ (car $5 \wedge 7 = 1$ et $\phi(7) = 6$).

    Donc on a $5^{160} \equiv 2 [7]$ et $5^{160} \equiv 1 [11]$.

    On peut utiliser le \textbf{théorème chinois des restes} pour résoudre ce système. Mais comme celui-ci n'a pas encore été vu, on va procéder par congruences successives.

    % à revoir absolument

    Nous cherchons $k_0 \in \Z$ tel que $k_0 \equiv \underbrace{1}_{\star}[11]$ et $k_0 \equiv \underbrace{2}_{*}[7]$.

    On a $11\wedge 7 = 1$, donc on peut écrire $11u + 7v = 1$.

    Et on a $11 \times 2 + 7 \times (-3) = 1$.

    On pose $k_0 = 11 \times 2 \times \underbrace{2}_{*} + 7 \times (-3) \times \underbrace{1}_{\star} = 23$.

    Donc $\begin{cases} 5^{160} \equiv 23[11] \\ 5^{160} \equiv 23[7] \end{cases}$

    Cela implique que $5^{160} \equiv 23 [77]$, sachant que $7\wedge 11 =1$.

\end{exercise}

\begin{theorem}
    Soit $x \in \N^*\setminus\{1\}$. Il existe $p_1,\dots,p_r \in \Pset$ tels que $x=\prod_{k=1}^{r}p_k$.
\end{theorem}

\begin{proof}
    Preuve par récurrence (forte) sur $x\in\N^*\setminus\{1\}$.

    \textbf{Initialisation :} Pour $x=2$, on a $2 \in \Pset$, donc la propriété est vraie.

    \textbf{Hérédité :} Supposons que la propriété soit vraie pour tout $k \in \N^*\setminus\{1\}$ tel que $2 \le k < x$, avec $x \ge 3$.

    Si $x+1 \in \Pset$, la propriété est vraie.

    Sinon, $\exists q \in \Pset \tq q \mid x+1$, ce qui implique que $x+1 = q \times a$ pour un certain $a \in \N^*\setminus\{1\} \tq a < x+1$.

    Cela implique que $a\le x$, donc en utilisant l'hypothèse de récurrence, on a $a = \prod_{k=1}^{r} p_k$ avec $p_1,\dots,p_r \in \Pset$.

    Donc $x+1 = q \times \prod_{k=1}^{r} p_k$, en posant $p_{r+1} = q$.
\end{proof}

\begin{definition}[Valuation $p$-adique d'un entier (déf. et théo.)]

    Soient $x \in \N^*\setminus\{1\}$ et $p \in \Pset$.

    Il existe un unique $\alpha \in \N$ et un unique $y \in \N^*$ tels que :

    $$\begin{cases}
        x = p^{\alpha} y\\
        p \wedge y = 1
    \end{cases}$$

    $\alpha$ est appelé la \textbf{valuation $p$-adique} de $x$, et notée $v_p(x)=\alpha$.

    $$v_p(x) = \max\{k \in \N \tq p^k \mid x\}$$
    
\end{definition}

\begin{proof}[Existence et unicité]
    \textbf{Démonstration de l'existence :}

    On pose $A = \{k \in \N \tq p^k \mid x\}$.

    \textbf{Démonstration de l'unicité :}

    Supposons que $x = p^{\alpha_1}y_1 = p^{\alpha_2}y_2$ avec $p \wedge y_1 = 1$ et $p \wedge y_2 = 1$.

    Supposons que $\alpha_1 \ne \alpha_2$.

    On posera $lambda = \alpha_1 - \alpha_2 > 0$ (sans perte de généralité).

    On aura donc $p^{\lambda} y_1 = y_2$.

    Ce qui implique que $p\mid y_2$, ce qui est une contradiction, car cela implique que $p = 1$.

    On en déduit que $\alpha_1 = \alpha_2$ et $y_1 = y_2$.
    
\end{proof}
\todo{continue}

\begin{property}
    Si $x=\prod_{i=1}^r  p_i^{\alpha_i}$ avec les $p_i$ des nombres premiers deux à deux distincts, alors $v_{p_i}(x) = \alpha_i$ pour tout $i \in \{1,\dots,r\}$, et $v_p(x) = 0$ pour tout $p \in \Pset\setminus\{p_1,\dots,p_r\}$.

    Et on a $\forall p \in \Pset\setminus\{p_1,\dots,p_r\}, v_p(x) = 0$ (les nombres premiers qui ne divisent pas $x$ ont une valuation nulle).
\end{property}

\begin{proof}
    On a $\forall i \in \{1,\dots,r\}, x = p_i^{\alpha_i}\cdot \underbrace{\prod_{\substack{k=1 \\ k\ne i}}^{r}p_k^{\alpha_k}}_{=y_i}$.

    Les $p_k$ (premiers) sont deux à deux distincts, donc $p_i \wedge \prod_{k=1~;~k\ne i}^{r}p_k^{\alpha_k} = 1$.

    Cela implique que $p_i \wedge y_i = 1$ pour tout $i \in \{1,\dots,r\}$.

    On en déduit que $v_{p_i}(x) = \alpha_i$ pour tout $i \in \{1,\dots,r\}$.

    Soit $p \in \Pset\setminus\{p_1,\dots,p_r\}$.

    On a $x=p^0 \cdot x$, et $p\notin\{p_1,\dots,p_r\} \implies \forall i, p\wedge p_i = 1 \implies p \wedge x = 1$.

    Donc $v_p(x) = 0$ pour tout $p \in \Pset\setminus\{p_1,\dots,p_r\}$.
\end{proof}

\section{Décomposition primaire et applications}

\begin{theorem}[Décomposition primaire]

    Soit $x\in \N^*\setminus\{1\}$.

    Il existe $p_1<\dots<p_r \in \Pset$ deux à deux distincts, et $\alpha_1,\dots,\alpha_r \in \N^*$ tels que $x = \prod_{k=1}^{r} p_k^{\alpha_k}$.

    Cette décomposition est unique.

    Si on n'impose pas l'ordre $p_1 < \dots < p_r$, alors la décomposition est unique à l'ordre/la permutation près.

    i.e. si $x=\prod_{i=1}^s q_i^{\beta_i}$ avec $q_1 < \dots < q_s \in \Pset$ et $\beta_j \in \N^* \forall j$, alors $r=s, \forall 1 \le i \le r : \begin{cases}
    p_i = q_i\\
    \alpha_i = \beta_i
    \end{cases}$
\end{theorem}

\begin{proof}
    L'existence a déjà été démontrée.

    \textbf{Démonstration de l'unicité :}

    Supposons que $x=\prod_{k=1}^r p_k^{\alpha_k} = \prod_{i=1}^s q_i^{\beta_i}$ avec $\begin{cases}p_1<\dots<p_r \in \Pset\\q_1<\dots<q_s \in \Pset\end{cases}$ et $\alpha_k,\beta_i \in \N^*$.

    Soit $k=1,\dots,r$. On a $p_k \mid \prod_{i=1}^s q_i^{\beta_i}$.

    On sait que $p_k$ est premier, donc $\exists i \in \{1,\dots,s\} \tq p_k \mid q_i^{\beta_i} \implies p_k \mid q_i$.

    Et on sait aussi que $q_i$ est premier, donc $p_k = q_i$, cela implique que $p_k = 1$ ou $p_k = q_i$.

    Donc $\{p_1,\dots,p_r\}\subset \{q_1,\dots,q_s\}$.

    De même, on trouve que $\{q_1,\dots,q_s\} \subset \{p_1,\dots,p_r\}$.

    Donc $\{p_1,\dots,p_r\} = \{q_1,\dots,q_s\}$, ce qui implique que $r=s$ et $p_i = q_i$ pour tout $i \in \{1,\dots,r\}$.

    On a $x = \prod_{k=1}^r p_k^{\alpha_k} = \prod_{i=1}^r p_i^{\beta_i}$.

    D'après la propriété précédente, on a $v_{p_i}(x) = \alpha_i$ et $v_{p_i}(x) = \beta_i$ pour tout $i \in \{1,\dots,r\}$.

    Donc $\alpha_i = \beta_i$ pour tout $i \in \{1,\dots,r\}$.

    On en déduit que la décomposition primaire de $x$ est unique.
\end{proof}

\begin{property}
    Soient $x,y \in \N^*\setminus\{1\}$.

    $$x\mid y \iff \forall p \in \Pset, v_p(x) \le v_p(y)$$
\end{property}
\label{prop:div_et_valuation}

\begin{proof}
    \textbf{($\implies$) :} Soit $p \in \Pset$. On a donc $x = p^\alpha \cdot z_1$ et $p\wedge z_1 = 1$, avec $\alpha = v_p(x)$.

    Comme $x \mid y$, on a $y = x \cdot k$ pour un certain $k \in \N$.

    De même, il existe un unique $\beta \in \N$, et un unique $z_2 \in \N^*$ tels que $k=p^\beta z_2$ ($\beta = v_p(k)$). On a $p \wedge z_2 = 1$.

    Donc $y = p^{\alpha + \beta} z_1 z_2$.

    Comme $p \wedge z_1 = 1$ et $p \wedge z_2 = 1$, on a $p \wedge z_1 z_2 = 1$.

    Donc $v_p(y) = \alpha + \beta \ge \alpha = v_p(x)$.

    \textbf{($\impliedby$) :} On a $x = \prod_{i = 1}^r p_i^{\alpha_i}$ et $y = \prod_{i=1}^r p_i^{\beta_i}$, avec $p_1,\dots,p_r \in \Pset$ et $\forall 1 \le i \le r, \alpha_i, \beta_i \ge 0$.

    On a $\forall 1 \le i \le r, \alpha_i \le \beta_i$ (parce que $v_{p_i}(x) \le v_{p_i}(y)$).

    Donc $y = \prod_{i=1}^r p_i^{\beta_i} = \prod_{i=1}^r p_i^{\alpha_i} \cdot \prod_{i=1}^r p_i^{\beta_i - \alpha_i} = x \cdot \underbrace{\prod_{i=1}^r p_i^{\beta_i - \alpha_i}}_{\in \N^*}$.

    Donc $x \mid y$.
\end{proof}

\begin{theorem}[Calcul du PGCD par décomposition primaire]
    Soient $x,y \in \N^*\setminus\{1\}$.

    On a $x = \prod_{i=1}^r p_i^{\alpha_i}$ et $y = \prod_{i=1}^r p_i^{\beta_i}$, avec $p_1,\dots,p_r \in \Pset$ et $\alpha_i, \beta_i \in \N$.

    Alors $x \wedge y = \prod_{i=1}^r p_i^{\min(\alpha_i,\beta_i)}$.
\end{theorem}

\begin{proof}
    On pose $d = \prod_{i=1}^r p_i^{m_i}$.

    On a $\forall 1 \le i \le r, m_i \le \alpha_i \et m_i \le \beta_i$.

    Alors $d \mid x$ et $d\mid y$ donc $d\mid x\wedge y$.

    On pose $d' = x \wedge y$, alors $d' \mid x$ et $d' \mid y$.

    Donc $\forall p \in \Pset, \begin{cases}
    v_p(d') \le v_p(x)\\
    v_p(d') \le v_p(y)
    \end{cases}$

    i.e. $\forall 1 \le i \le r, v_{p_i}(d') \le \alpha_i$ et $v_{p_i}(d') \le \beta_i$.

    Donc $\forall 1 \le i \le r, v_{p_i}(d') \le \min(\alpha_i,\beta_i) = m_i$.

    D'après la propriété précédente, on a $d' \mid d$.

    On a $d \mid d'$ et $d' \mid d$, donc $d = d'$, car ils sont tous les deux positifs.

    On en déduit que $x \wedge y = \prod_{i=1}^r p_i^{\min(\alpha_i,\beta_i)}$.
\end{proof}

\begin{exercise}
    Soient $x,y \in \N^*$. Montrer que $x\mid y \iff x^2 \mid y^2$.

    \textbf{Solution :}

    On va procéder par équivalences successives en utilisant la propriété \ref{prop:div_et_valuation}.

    \begin{align*}
        x^2 \mid y^2 &\iff \forall p \in \Pset, v_p(x^2) \le v_p(y^2)\\
        &\iff \forall p \in \Pset, 2v_p(x) \le 2v_p(y)\\
        &\iff \forall p \in \Pset, v_p(x) \le v_p(y)\\
        &\iff x \mid y \text{ CQFD.}
    \end{align*}

    On a utilisé le fait que $v_p(x^2) = 2v_p(x)$ et $v_p(y^2) = 2v_p(y)$, ce qui est une conséquence de la définition de la valuation $p$-adique (et de la décomposition primaire).
\end{exercise}

\begin{remark}[PGCD de $a^n,b^n$]
    Soient $a,b \in \N^*$ et $n \in \N^*$. Alors
    \[
        a^n \wedge b^n = (a \wedge b)^n.
    \]
\end{remark}

\chapter{Plus petit commun multiple}

\begin{definition}[PPCM (déf. et théorème)]

    Soient $A$ un anneau principal et $x_1,\dots,x_n \in A$, alors $\exists m \in A \tq \cap_{i=1}^n x_i A = mA$, avec :

    $$
        \forall 1 \le i \le n, x_i \mid m\\
        \si M \text{ est un autre multiple commun des } (x_i)_i, \text{ alors } m \mid M
    $$

    $m$ est appelé le \textbf{plus petit commun multiple} (PPCM) des $x_i$ et noté $\ppcm(x_1,\dots,x_n)$, ou encore $x_1 \vee x_2 \vee \dots \vee x_n$.
    
\end{definition}

\begin{proof}
    $\forall 1 \le i \le n, x_i A$ est un idéal de $A$.
    
    Donc $\cap_{i=1}^n x_i A$ est un idéal de $A$, qui est un anneau principal.

    $\implies \cap_{i=1}^n x_i A$ est un idéal principal.

    i.e. $\exists m \in A \tq \cap_{i=1}^n x_i A = mA$.

    Donc $\forall 1 \le i \le n, mA \subset x_i A \implies x_i \mid m$.

    Si $\exists M \tq \forall 1 \le i \le n, x_i \mid M$, alors $M \in x_i A$ pour tout $i$. 

    Donc $MA \subset \cap_{i=1}^n x_i A = mA$.

    Donc $m \mid M$.
\end{proof}

\begin{remark}
    \begin{itemize}
        \item Si $m$ est un ppcm des $x_i$, alors les autres ppcm sont les éléments associés à $m$.

        \item Dans le cas de $\Z$, le ppcm est unique (on choisit le ppcm positif, ce qu'on appelle le ``générateur positif'').
    \end{itemize}
\end{remark}

\begin{property}
    \begin{enumerate}
        \item $\forall x,y \in \Z, \forall \lambda \in \Z, (\lambda x) \vee (\lambda y) = \abs{\lambda} (x \vee y)$.
        \item Si $x,y \in \Z \tqp x \wedge y = 1$, alors $x \vee y = \abs{x}\cdot\abs{y}$.
        \item $\forall x,y\in\Z, (x \wedge y) \cdot (x \vee y) = \abs{x}\cdot\abs{y}$.
    \end{enumerate}
\end{property}

\begin{proof}
    \textbf{Preuve du premier point :}

    \begin{align*}
    (\lambda x)\Z \cap (\lambda y)\Z &= (\lambda x \vee \lambda y)\Z\\
    \lambda (x\Z \cap y\Z) &= \lambda(x \vee y)\Z\\
    (\lambda x \vee \lambda y)\Z &= \lambda (x \vee y)\Z\\
    \implies (\lambda x) \vee (\lambda y) &= \abs{\lambda} (x \vee y)
    \end{align*}

    \textbf{Preuve du deuxième point :}

    On pose $m= x \vee y$.

    Donc $x\mid m$ et $y \mid m$.

    Comme $x \wedge y = 1$, on a $xy \mid m$ (propriété de l'application).

    Et on a $m \mid xy$ (car $m \mid x$ et $m \mid y$).

    Donc $m = \abs{xy}$.

    \textbf{Preuve du troisième point :}

    On pose $d=x \wedge y$, donc $\exists x_1,y_1 \in \Z \tqp x= dx_1, y=dy_1 \et x_1 \wedge y_1 = 1$.

    Donc, d'après le deuxième point, on a $x_1 \vee y_1 = \abs{x_1}\cdot\abs{y_1}$.

    Donc $d^2(x_1 \vee y_1) = d^2 \abs{x_1}\cdot\abs{y_1}$.

    Donc $\abs{d}(dx_1 \vee dy_1) = \abs{dx_1}\cdot\abs{dy_1}$.

    Donc $(x \wedge y)(x \vee y) = \abs{x}\cdot\abs{y}$.
\end{proof}

\begin{theorem}
    Soient $x = \prod_{i=1}^{r}p_i^{\alpha_i}$ et $y = \prod_{i=1}^{r} p_i^{\beta_i}$, avec $p_1,\dots,p_r \in \Pset$ et $\alpha_i,\beta_i \in \N$.

    Alors $x \vee y = \prod_{i=1}^{r} p_i^{\max(\alpha_i,\beta_i)}$.
\end{theorem}

\begin{proof}
    On a $xy = \prod_{i=1}^{r}p_i^{\alpha_i + \beta_i}$.

    Or $x \vee y = \frac{xy}{x\wedge y}$.

    Donc $x \vee y = \prod_{i=1}^{r} p_i^{\alpha_i + \beta_i - \min(\alpha_i,\beta_i)} = \prod_{i=1}^{r} p_i^{\max(\alpha_i,\beta_i)}$.

    Sachant que $\alpha_i + \beta_i - \min(\alpha_i,\beta_i) = \max(\alpha_i,\beta_i)$.
\end{proof}

\begin{center}
    \rule{0.5\textwidth}{1pt}\\
    Fin du Chapitre XI.\\
    \rule{0.5\textwidth}{1pt}
\end{center}

\end{document}